/**
 * 给定一个数组nums，如果i < j且nums[i] > 2*nums[j]我们就将(i, j)称作一个重要翻转对。
 *
 * 你需要返回给定数组中的重要翻转对的数量。
 *
 * 链接：https://leetcode.cn/problems/reverse-pairs
 * 思路：归并排序
 * 详解：https://labuladong.gitee.io/algo/2/21/41/
 */
class ReversePairs {
    public int reversePairs(int[] nums) {
        return mergeSort(nums,0,nums.length-1);
    }
    public int mergeSort(int[] nums,int left,int right) {
        if(left>=right) {
            return 0;
        }
        int mid=left+((right-left)>>>1);
        int leftCount=mergeSort(nums,left,mid);
        int rightCount=mergeSort(nums,mid+1,right);
        int count=merge(nums,left,mid,right);
        return leftCount+rightCount+count;
    }
    public int merge(int[] nums,int left,int mid,int right) {
        int s1=left,b1=mid;
        int s2=mid+1,b2=right;
        int count=0;
        int[] tmp=new int[right-left+1];
        int k=0;
        int end=mid+1;
        for(int i=left;i<=mid;i++) {
            while(end<=right&&(long)nums[i]>(long)2*nums[end]) {
                end++;
            }
            count+=(end-mid-1);
        }
        //合并
        while(s1<=b1&&s2<=b2) {
            if(nums[s1]<=nums[s2]) {
                tmp[k++]=nums[s1++];
            } else {
               
                tmp[k++]=nums[s2++];
            }
        }
        while(s1<=b1) {
            tmp[k++]=nums[s1++];
        }
        while(s2<=b2) {
            tmp[k++]=nums[s2++];
        }
        for(int i=0;i<k;i++) {
            nums[i+left]=tmp[i];
        }
        return count;
    }
}